1414. Камешки

 

Закон Джунглей говорит очень ясно, что каждый волк, обзаводясь семьей, может покинуть свою Стаю. Но как только его волчата подрастут и станут на ноги, он должен привести их на Совет Стаи, который собирается обычно раз в месяц, во время полнолуния, и показать всем другим волкам.

 

Отец Волк подождал, пока его волчата подросли и начали понемногу бегать, и в одну из тех ночей, когда собиралась Стая, повел волчат, Маугли и Мать Волчицу на Скалу Совета. Это была вершина холма, усеянная большими валунами, за которыми могла укрыться целая сотня волков. Акела, большой серый волк-одиночка, избранный вожаком всей Стаи за силу и ловкость взывал со своей скалы:

– Закон вам известен, Закон вам известен! Смотрите же, волки!

Отец Волк вытолкнул на середину круга Лягушонка Маугли. Усевшись на землю, Маугли засмеялся и стал играть камешками, блестевшими в лунном свете. Игра заключалась в следующем. Он мог взять k1 или k2 или k3 или … kn камешков из одной кучки камней и положить их в другую кучку, а также из второй кучки переложить обратно в первую k1 или k2 или k3 или … kn камешков. Ему было интересно, можно ли во второй кучке получить ровно m камешков.

 

Вход. Первая строка содержит два числа n и m (2 ≤ n ≤ 1000, 2 ≤ m ≤ 2·109). Во второй строке записаны n натуральных чисел k1, k2, k3, …, kn (ki ≤ 2·109).

 

Выход. Вывести «YES», если во второй кучке можно получить m камешков и «NO» в противном случае.

 

Пример входа

Пример выхода

3 10

12 8 6

YES

 

 

РЕШЕНИЕ

НОД

 

Анализ алгоритма

Ответ будет утвердительный, если m делится на НОД натуральных чисел k1, k2, k3, …, kn.

 

Реализация алгоритма

Читаем входные данные. Вычисляем наибольший общий делитель d входных чисел.

 

scanf("%d %d",&n,&m);

scanf("%d",&d);

while(n-- > 1)

{

  scanf("%d",&a);

  d = gcd(d,a);

}

 

Если m делится на d, то ответ YES. Иначе ответ NO.

 

if (m % d == 0) puts("YES"); else puts("NO");